class HashTable<T = any> {
  private storage: [string, T][][] = [];
  private length: number = 7; // 哈希表长度（初始设为质数 7）
  private count: number = 0; // 当前存放的元素个数
  private loadFactor: number = 0.75; // 扩容因子
  private minLoadFactor: number = 0.25; // 缩放因子

  put(key: string, value: T) {
    const index = this.hashFunc(key, this.length);
    let bucket = this.storage[index];
    if (bucket === undefined) {
      bucket = [];
      this.storage[index] = bucket;
    }

    for (let tuple of bucket) {
      if (tuple[0] === key) {
        return (tuple[1] = value);
      }
    }

    bucket.push([key, value]);
    this.count++;

    if (this.count / this.length > this.loadFactor) {
      this.resize(this.getPrime(this.length * 2));
    }
  }

  get(key: string): T | undefined {
    const index = this.hashFunc(key, this.length);
    const bucket = this.storage[index];
    if (bucket === undefined) return undefined;

    for (const [tupleKey, tupleValue] of bucket) {
      if (key === tupleKey) return tupleValue;
    }

    return undefined;
  }

  delete(key: string) {
    const index = this.hashFunc(key, this.length);
    const bucket = this.storage[index];
    if (!bucket) return undefined;

    for (let i = 0; i < bucket.length; i++) {
      const [tupleKey, tupleValue] = bucket[i];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;

        if (this.count / this.length < this.minLoadFactor && this.length > 7) {
          this.resize(this.getPrime(Math.floor(this.length / 2)));
        }

        return tupleValue;
      }
    }

    return undefined;
  }

  private isPrime(num: number): boolean {
    for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i === 0) return false;
    }
    return true;
  }

  private getPrime(num: number): number {
    while (!this.isPrime(num)) {
      num++;
    }

    return num;
  }

  private resize(newLength: number) {
    this.length = Math.max(newLength, this.length);
    const oldStorage = this.storage;
    this.storage = [];
    this.count = 0;

    for (const bucket of oldStorage) {
      if (bucket) {
        for (const [key, value] of bucket) {
          this.put(key, value);
        }
      }
    }
  }

  size() {
    return this.count;
  }

  /**
   * 哈希函数
   * @param key 转换的key
   * @param max 数组最大长度
   * @returns 索引值
   */
  hashFunc(key: string, max = 7): number {
    let hashCode = 0;
    const length = key.length;
    for (let i = 0; i < length; i++) {
      hashCode += 31 * hashCode + key.charCodeAt(i);
    }

    return hashCode % max;
  }
}
